// 位运算
// 位运算最关键的几个操作：
// 1.取最右边的 ‘1’：num &= (-num)
// 2.消除最右边的 ‘1‘：num &= (num - 1)
// 3.异或运算 ^：相同为 0（消消乐），不同为 1，无进位相加
// 4.位图的思想：如果题目中提出要求不适用额外的数据结构，那么大概率是要使用位图了
// 5.检查某一个 bit：(num >> x) & 1 == 1
// 6.设置某一个 bit：num |= (1 << x);

// 例题 1：
//实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
//
//        示例 1：
//
//        输入: s = "leetcode"
//        输出: false
//        示例 2：
//
//        输入: s = "abc"
//        输出: true
//        限制：
//
//        0 <= len(s) <= 100
//        s[i]仅包含小写字母
//        如果你不使用额外的数据结构，会很加分。

// 解题思路：
// 看到题目首先想到哈希表，用哈希表统计字符出现的次数，
// 如果某个字符出现的次数大于 1，返回 false，
// 如果遍历完字符串也没返回 false，则返回 true

// 题目要求不使用额外的数据结构，那么就不能使用哈希表了，但是解题思路不变，代替哈希表的就是位图
// 使用一个整数的 32 个比特位代替，1 表示该字符出现过，0 表示该字符没有出现过
// 题目涉及检查某一个 bit：(num >> x) & 1 == 1
// 以及设置某一个 bit：num |= (1 << x);

public class IsUnique {
    public boolean isUnique(String astr) {
        int hash = 0;
        int m = astr.length();
        if(m > 26) return false;// 鸽巢原理
        for(int i = 0; i <  m; i++){
            char ch = astr.charAt(i);
            int n = ch - 'a';
            if(((hash >> n) & 1) == 1) return false;
            hash |= (1 << ch - 'a');
        }
        return true;
    }
}